﻿#include "maze.h"

/*
* 迷宫寻路
*
* 使用穷举法，找到一条可行通路即返回
*/
Status MazePath(MazeType maze, PosType start, PosType end)
{
	SqStack S;
	PosType curPos;
	SElemType e;

	InitStack(&S);
	
	curPos = start;//设置当前位置是入口位置

	do {
		//如果当前位置是可以通过的（该位置是从未曾探索过的通道块）
		if (Pass(maze, curPos))
		{
			//留下足迹（留下向东访问的标记）
			FootPrint(maze, curPos);

			e = Construct(curPos,East);//构造一个通道块信息并返回

			Push(&S, e);//将通道块压入栈
			if (Equals(curPos, end))
			{
				printf("\n寻路成功！！\n\n");
				return TRUE;
			}

			curPos = NextPos(curPos, East);//获取下一个要探索的位置

		}
		else
		{
			if (!StackEmpty(S))
			{
				Pop(&S, &e);//退回上一个位置

				while (e.di == North && !StackEmpty(S))
				{
					MarkPrint(maze, e.seat, Impasse);//留下死胡同印记

					Pop(&S, &e);//继续退回
				}
				if (e.di < North)
				{
					++e.di;//改变探索方向，按东南西北方向轮询

					MarkPrint(maze, e.seat, e.di);//在迷宫下留下访问标记，用来观察迷宫的状态
					Push(&S, e);//从新将该位置加入到路径只能
					curPos = NextPos(e.seat, e.di);
				}
			}
		}
	} while (!StackEmpty(S));

	printf("\n寻路失败\n\n");

	return FALSE;
}

/*
 * 初始化一个规模为M×N迷宫
 * start和end分别为迷宫的入口坐标和出口坐标
 */
void InitMaze(MazeType maze, PosType* start, PosType* end)
{
	int tmp;
	srand((unsigned)time(NULL));       //初始化随机数发生器
	for (int i=0;i < M;i++)
	{
		for (int j = 0;j < N;j++)
		{
			if (i == 0 || j == 0 || i == M - 1 || j == N - 1)
				maze[i][j] = Wall;//外墙
			else
			{
				tmp = rand() % X;
				if (tmp == 0)
					maze[i][j] = Obstacle;//内墙
				else
					maze[i][j] = Way;//通路
			}
		}
	}
	//入口
	start->x = 1;
	start->y = 0;
	//出口
	end->x = M - 2;
	end->y = N - 1;
	//开放入口和出口
	maze[1][0] = maze[M - 2][N - 1] = Way;
	//提高寻路成功率
	maze[1][1] = maze[M - 2][N - 2] = Way;

	// 显示迷宫的初始状态
	PrintMaze(maze);
}

/*
 * 判断当前位置是否可通过：要求该位置是从未曾探索的通道块
 *
 */
Status Pass(MazeType maze, PosType seat)
{
	int x = seat.x;
	int y = seat.y;

	if (x < 0 || y < 0 || x > M - 1 || y > N - 1)
		return FALSE;

	if (maze[x][y] != Way)
		return FALSE;

	return TRUE;

	/*for (int i = 0; i < M; i++)
	{
		for (int j = 0;j < N; j++)
		{
			if (maze[i][j] == seat.x && maze[i][j] == seat.y)
				return TRUE;
		}	
	}*/
}

/*
 * 获取下一个应当探索的位置
 * di指示当前所处位置的探索方向，包括East, South, West, North
 */
PosType NextPos(PosType seat, MazeNode di)
{
	PosType tmp = seat;
	switch (di)
	{
		case East://东
			tmp.y++;
			break;
		case South://南
			tmp.x++;
			break;
		case West://西
			tmp.y--;
			break;
		case North:
			tmp.x--;
			break;
	}
	return tmp;
}

/*
 * 留下初始访问足迹
 *
 * 初始访问足迹即向东访问
 */
void FootPrint(MazeType maze, PosType seat)
{
	MarkPrint(maze, seat, East);
}

/*
 * 在迷宫的seat处留下mark标记
 *
 */
void MarkPrint(MazeType maze, PosType seat, int mark)
{
	maze[seat.x][seat.y] = mark;
	// 绘制迷宫
	PrintMaze(maze);
}
void Wait(long time) {
	double i;

	if (time < 0) {
		time = -time;
	}

	for (i = 0.01; i <= 100000.0 * time; i += 0.01) {
		// 空循环
	}
}

/*
 * 构造一个通道块信息并返回
 *
 */
 SElemType Construct( PosType seat, int di) {
 	SElemType e;
 
 	//e.ord = ord;
 	e.seat = seat;
 	e.di = di;
 
 	return e;
 }
//SElemType Construct(int ord, PosType seat, int di) {
//	SElemType e;
//
//	e.ord = ord;
//	e.seat = seat;
//	e.di = di;
//
//	return e;
//}

/*
 * 绘制迷宫
 * 以图形的方式呈现迷宫当前的状态
 *
 */
void PrintMaze(MazeType maze)
{
	Wait(SleepTime);
	system("cls");					// 先清除屏幕现有内容
	for (int i = 0;i < M;i++)
	{
		for (int j = 0;j < N;j++)
		{
			switch (maze[i][j])
			{
				case Wall:
					printf("*");
					break;
				case Obstacle:
					printf("*");
					break;
				case East:
					printf("6");
					break;
				case South:
					printf("2");
					break;
				case West:
					printf("4");
					break;
				case North:
					printf("8");
					break;
				case Impasse:
					printf("0");
					break;
				default:
					printf(" ");
			}
			if (j != 0 && j % (N - 1) == 0)
				printf("\n");//每一行最后一个元素
		}
	}
	printf("\n");
}

/*
 * 判断两个坐标是否相等
 *
 */
Status Equals(PosType a, PosType b)
{
	if (a.x == b.x && a.y == b.y)
		return TRUE;
	return FALSE;
}